package com.squirrel.michale;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/4 9:23 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2556 {

    public boolean isPossibleToCutPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for (int i = m-1; i >=0 ; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) {
                    continue;
                }
                if ((i + 1 >= m || grid[i + 1][j] == 0) && (j + 1 >= n || grid[i][j + 1] == 0)) {
                    grid[i][j] = 0;
                }
            }
        }
        if (grid[0][0] == 0) {
            return true;
        }
        int x1= 0;
        int y1 = 0;
        int x2 = 0;
        int y2 = 0;
        for (int k = 0; k < m + n - 3; k++) {

            if (y1 + 1 < n && grid[x1][y1+1] == 1) {
                y1++;
            }else {
                x1++;
            }
            if (x2+1<m && grid[x2 + 1][y2] == 1) {
                x2++;
            }else{
                y2++;
            }
            if (x1 == x2 && y1 == y2) {
                return true;
            }
        }
        return false;
    }

    public boolean isPossibleToCutPath2(int[][] grid) {
        int m = grid[0].length;
        int n = grid.length;
        for (int i = m-1; i >=0 ; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) {
                    continue;
                }
                 if ((j - 1 >= 0 && grid[i][j - 1] == 0) && (i - 1 >= 0 && grid[i-1][j] == 0)) {
                    grid[i][j] = 0;
                }
            }
        }
        if (grid[0][0] == 0) {
            return true;
        }

        int x1= 0;
        int y1 = 0;
        int x2 = 0;
        int y2 = 0;
        for (int k = 0; k < m + n - 3; k++) {

            if (y1 + 1 < n && grid[x1][y1] == 1) {
                y1++;
            }else {
                x1++;
            }
            if (x2+1<m && grid[x2 + 1][y2] == 1) {
                x2++;
            }else{
                y2++;
            }
            if (x1 == x2 && y1 == y2) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {

        LeetCode2556 leetCode2556 = new LeetCode2556();

        int[][] grid = new int[][]{{1, 1, 1}, {1, 0, 0}, {1, 1, 1}};
        System.out.println(leetCode2556.isPossibleToCutPath(grid));


        int[][] grid2 = new int[][]{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        System.out.println(leetCode2556.isPossibleToCutPath(grid2));


        int[][] grid3 = new int[][]{{1,1,1,0,0},{1,0,1,0,0},{1,1,1,1,1},{0,0,1,1,1},{0,0,1,1,1}};
        System.out.println(leetCode2556.isPossibleToCutPath(grid3));
    }
}
